UVa/11488 - Hyper prefix sets/11488.cpp

   1 /*
   2   Time-limit exceeded.
   3
   4   Problem: 11488 - Hyper prefix sets
   5   Author: Andrés Mejía-Posada
   6  */
   7
   8 #include <algorithm>
   9 #include <iterator>
  10 #include <iostream>
  11 #include <sstream>
  12 #include <fstream>
  13 #include <cassert>
  14 #include <climits>
  15 #include <cstdlib>
  16 #include <cstring>
  17 #include <string>
  18 #include <cstdio>
  19 #include <vector>
  20 #include <cmath>
  21 #include <queue>
  22 #include <deque>
  23 #include <stack>
  24 #include <map>
  25 #include <set>
  26 using namespace std;
  27
  28 int dp[50001][201];
  29 string s[50001];
  30
  31 #define V(x, t, d) copy(x.begin(), x.end(), ostream_iterator<t>(cout, d)); cout << endl
  32
  33 int main(){
  34   int C;
  35   cin >> C;
  36   while (C--){
  37     int n;
  38     cin >> n;
  39     int maxLen = -1;
  40     for (int i=0; i<n; ++i) cin >> s[i], maxLen = max(maxLen, (int)s[i].length());
  41     sort(s, s + n);
  42
  43     //V(s, string, "\n");
  44
  45     //for (int i=0; i<n; ++i) for (int j=0; j<=maxLen; ++j) dp[i][j] = 0;
  46
  47     for (int j=0; j<s[0].size(); ++j) dp[0][j] = 1;
  48     for (int i=1; i<n; ++i) dp[i][0] = 1 + (s[i][0] == s[i-1][0] ? dp[i-1][0] : 0);
  49
  50     int ans = -1;
  51     for (int i=1; i<n; ++i){
  52       for (int j=1, m = s[i].size(); j<m; ++j){
  53         dp[i][j] = 1;
  54         if (j < s[i-1].length() && s[i][j] == s[i-1][j] &&
  55             dp[i][j-1] > dp[i-1][j-1]){
  56           dp[i][j] += dp[i-1][j];
  57         }
  58         ans = max(ans, (j+1)*dp[i][j]);
  59       }
  60     }
  61
  62 //     for (int i=0; i<n; ++i){
  63 //       for (int j=0; j<maxLen; ++j){
  64 //      printf("%1d ", dp[i][j]);
  65 //       }
  66 //       cout << endl;
  67 //     }
  68
  69
  70     cout << ans << endl;
  71
  72   }
  73   return 0;
  74 }